// Go作者版权所有。版权所有。
// 此源代码的使用受BSD样式的约束
// 可以在许可证文件中找到的许可证。

package ssa

import (
	"cmd/compile/internal/reflectdata"
	"cmd/compile/internal/types"
	"cmd/internal/obj"
	"cmd/internal/objabi"
	"cmd/internal/src"
	"fmt"
)

// 零区域记录对象中已知为零的部分。
// 零区域仅适用于单个内存状态。
// 如果掩码中对应的指针大小的字
// 已知基础对象为零。
// 换句话说，如果掩码&（1<<i）！=0，然后[base+i*ptrSize，base+（i+1）*ptrSize）
// 已知为零。
type ZeroRegion struct {
	base *Value
	mask uint64
}

// needwb报告存储操作v是否需要写屏障。
// v必须是存储/移动/零。
// 零提供已知的零信息（由内存类型值的ID键入）。
func needwb(v *Value, zeroes map[ID]ZeroRegion) bool {
	t, ok := v.Aux.(*types.Type)
	if !ok {
		v.Fatalf("store aux is not a type: %s", v.LongString())
	}
	if !t.HasPointers() {
		return false
	}
	if IsStackAddr(v.Args[0]) {
		return false // 栈上写不需要写屏障
	}
	if v.Op == OpMove && IsReadOnlyGlobalAddr(v.Args[1]) {
		if mem, ok := IsNewObject(v.Args[0]); ok && mem == v.MemoryArg() {
			// 将数据从只读内存复制到新对象不需要写屏障。
			return false
		}
	}
	if v.Op == OpStore && IsGlobalAddr(v.Args[1]) {
		// 将指向非堆位置的指针存储到零内存中不需要写屏障。
		ptr := v.Args[0]
		var off int64
		size := v.Aux.(*types.Type).Size()
		for ptr.Op == OpOffPtr {
			off += ptr.AuxInt
			ptr = ptr.Args[0]
		}
		ptrSize := v.Block.Func.Config.PtrSize
		if off%ptrSize != 0 || size%ptrSize != 0 {
			v.Fatalf("unaligned pointer write")
		}
		if off < 0 || off+size > 64*ptrSize {
			// 冲销跟踪偏移的末尾
			return true
		}
		z := zeroes[v.MemoryArg().ID]
		if ptr != z.base {
			return true
		}
		for i := off; i < off+size; i += ptrSize {
			if z.mask>>uint(i/ptrSize)&1 == 0 {
				return true // 不知道是零
			}
		}
		// 已知所有写入位置都是零写入屏障，不需要。
		return false
	}
	return true
}

// 写载体过程为存储操作（存储、移动、零）插入写屏障
// 必要时（上述条件）。它将存储操作重写为分支
// 还有运行时调用，比如
// None
// 如果已启用写载体{
// gcWriteBarrier（ptr，val）
// }否则{
// *ptr=val
// }
// None
// 将为单个类型的多个指针字段创建WB存储序列
// 通过单个分支一起发射。
func writebarrier(f *Func) {
	if !f.fe.UseWriteBarrier() {
		return
	}

	var sb, sp, wbaddr, const0 *Value
	var typedmemmove, typedmemclr, gcWriteBarrier *obj.LSym
	var stores, after []*Value
	var sset *sparseSet
	var storeNumber []int32

	zeroes := f.computeZeroMap()
	for _, b := range f.Blocks { // 范围循环是安全的，因为我们添加的块不包含要扩展的存储
		// 首先，确定需要插入写屏障的所有存储。
		// 暂时用WB ops标记它们。记录WB ops的存在。
		nWBops := 0 // 在当前块中仍要重写的临时创建的WB ops计数
		for _, v := range b.Values {
			switch v.Op {
			case OpStore, OpMove, OpZero:
				if needwb(v, zeroes) {
					switch v.Op {
					case OpStore:
						v.Op = OpStoreWB
					case OpMove:
						v.Op = OpMoveWB
					case OpZero:
						v.Op = OpZeroWB
					}
					nWBops++
				}
			}
		}
		if nWBops == 0 {
			continue
		}

		if wbaddr == nil {
			// 延迟初始化写屏障测试和调用的全局值
			// 在输入块中查找SB和SP值
			initpos := f.Entry.Pos
			sp, sb = f.spSb()
			wbsym := f.fe.Syslook("writeBarrier")
			wbaddr = f.Entry.NewValue1A(initpos, OpAddr, f.Config.Types.UInt32Ptr, wbsym, sb)
			gcWriteBarrier = f.fe.Syslook("gcWriteBarrier")
			typedmemmove = f.fe.Syslook("typedmemmove")
			typedmemclr = f.fe.Syslook("typedmemclr")
			const0 = f.ConstInt32(f.Config.Types.UInt32, 0)

			// 分配用于计算存储顺序的辅助数据结构
			sset = f.newSparseSet(f.NumValues())
			defer f.retSparseSet(sset)
			storeNumber = make([]int32, f.NumValues())
		}

		// 存储顺序中的订单值
		b.Values = storeOrder(b.Values, sset, storeNumber)

		firstSplit := true
	again:
		// 查找最后一个连续WB存储序列的开始和结束。
		// 将在那里插入一个分支。之后的值将被移动
		// 去一个新街区。
		var last *Value
		var start, end int
		values := b.Values
	FindSeq:
		for i := len(values) - 1; i >= 0; i-- {
			w := values[i]
			switch w.Op {
			case OpStoreWB, OpMoveWB, OpZeroWB:
				start = i
				if last == nil {
					last = w
					end = i + 1
				}
			case OpVarDef, OpVarLive, OpVarKill:
				continue
			default:
				if last == nil {
					continue
				}
				break FindSeq
			}
		}
		stores = append(stores[:0], b.Values[start:end]...) // 复制以避免混淆
		after = append(after[:0], b.Values[end:]...)
		b.Values = b.Values[:start]

		// 在WB存储之前查找内存
		mem := stores[0].MemoryArg()
		pos := stores[0].Pos
		bThen := f.NewBlock(BlockPlain)
		bElse := f.NewBlock(BlockPlain)
		bEnd := f.NewBlock(b.Kind)
		bThen.Pos = pos
		bElse.Pos = pos
		bEnd.Pos = b.Pos
		b.Pos = pos

		// 为端块设置控制流
		bEnd.CopyControls(b)
		bEnd.Likely = b.Likely
		for _, e := range b.Succs {
			bEnd.Succs = append(bEnd.Succs, e)
			e.b.Preds[e.i].b = bEnd
		}

		// 设置写屏障测试的控制流
		// 加载字、测试字，避免从加载字节写入部分寄存器。
		cfgtypes := &f.Config.Types
		flag := b.NewValue2(pos, OpLoad, cfgtypes.UInt32, wbaddr, mem)
		flag = b.NewValue2(pos, OpNeq32, cfgtypes.Bool, flag, const0)
		b.Kind = BlockIf
		b.SetControl(flag)
		b.Likely = BranchUnlikely
		b.Succs = b.Succs[:0]
		b.AddEdgeTo(bThen)
		b.AddEdgeTo(bElse)
		// TODO:对于OpStoreWB和缓冲写屏障，
		// 我们可以将写入移出写入屏障，
		// 这将导致更少的分支。我们可以做
		// 类似于OpZeroWB的东西，因为运行时
		// 能提供一半的屏障，然后我们
		// 可以无条件地执行OpZero（这可能
		// 还可以生成更好的归零代码）。OpMoveWB是
		// 更棘手，需要改变方法
		// CGOCHECKMEMOVE工程。
		bThen.AddEdgeTo(bEnd)
		bElse.AddEdgeTo(bEnd)

		// 对于每个写屏障存储，将写屏障版本附加到bThen
		// 和简单的商店版本到比利时
		memThen := mem
		memElse := mem

		// 如果MoveWB的源是易失性的（将被
		// 函数调用），我们需要将其复制到临时位置，如
		// 封送typedmemmove的参数可能会破坏我们正在处理的值
		// 试图移动。
		// 查找易失性源，在我们发出任何消息之前将其复制到临时文件
		// 呼叫
		// 不太可能有一个以上的。做一个线性规划
		// 搜索而不是使用地图。
		type volatileCopy struct {
			src *Value // 原始易失性值的地址
			tmp *Value // 我们已将易失性值复制到的临时文件的地址
		}
		var volatiles []volatileCopy
	copyLoop:
		for _, w := range stores {
			if w.Op == OpMoveWB {
				val := w.Args[1]
				if isVolatile(val) {
					for _, c := range volatiles {
						if val == c.src {
							continue copyLoop // 已复制
						}
					}

					t := val.Type.Elem()
					tmp := f.fe.Auto(w.Pos, t)
					memThen = bThen.NewValue1A(w.Pos, OpVarDef, types.TypeMem, tmp, memThen)
					tmpaddr := bThen.NewValue2A(w.Pos, OpLocalAddr, t.PtrTo(), tmp, sp, memThen)
					siz := t.Size()
					memThen = bThen.NewValue3I(w.Pos, OpMove, types.TypeMem, siz, tmpaddr, val, memThen)
					memThen.Aux = t
					volatiles = append(volatiles, volatileCopy{val, tmpaddr})
				}
			}
		}

		for _, w := range stores {
			ptr := w.Args[0]
			pos := w.Pos

			var fn *obj.LSym
			var typ *obj.LSym
			var val *Value
			switch w.Op {
			case OpStoreWB:
				val = w.Args[1]
				nWBops--
			case OpMoveWB:
				fn = typedmemmove
				val = w.Args[1]
				typ = reflectdata.TypeLinksym(w.Aux.(*types.Type))
				nWBops--
			case OpZeroWB:
				fn = typedmemclr
				typ = reflectdata.TypeLinksym(w.Aux.(*types.Type))
				nWBops--
			case OpVarDef, OpVarLive, OpVarKill:
			}

			// 然后阻塞：发出写屏障调用
			switch w.Op {
			case OpStoreWB, OpMoveWB, OpZeroWB:
				if w.Op == OpStoreWB {
					memThen = bThen.NewValue3A(pos, OpWB, types.TypeMem, gcWriteBarrier, ptr, val, memThen)
				} else {
					srcval := val
					if w.Op == OpMoveWB && isVolatile(srcval) {
						for _, c := range volatiles {
							if srcval == c.src {
								srcval = c.tmp
								break
							}
						}
					}
					memThen = wbcall(pos, bThen, fn, typ, ptr, srcval, memThen, sp, sb)
				}
				// 注意，我们设置了一个写载波函数调用。
				f.fe.SetWBPos(pos)
			case OpVarDef, OpVarLive, OpVarKill:
				memThen = bThen.NewValue1A(pos, w.Op, types.TypeMem, w.Aux, memThen)
			}

			// else块：普通存储
			switch w.Op {
			case OpStoreWB:
				memElse = bElse.NewValue3A(pos, OpStore, types.TypeMem, w.Aux, ptr, val, memElse)
			case OpMoveWB:
				memElse = bElse.NewValue3I(pos, OpMove, types.TypeMem, w.AuxInt, ptr, val, memElse)
				memElse.Aux = w.Aux
			case OpZeroWB:
				memElse = bElse.NewValue2I(pos, OpZero, types.TypeMem, w.AuxInt, ptr, memElse)
				memElse.Aux = w.Aux
			case OpVarDef, OpVarLive, OpVarKill:
				memElse = bElse.NewValue1A(pos, w.Op, types.TypeMem, w.Aux, memElse)
			}
		}

		// 马克死了
		for _, c := range volatiles {
			tmpNode := c.tmp.Aux
			memThen = bThen.NewValue1A(memThen.Pos, OpVarKill, types.TypeMem, tmpNode, memThen)
		}

		// 合并记录
		// 将存储器Phi拼接到原始序列的最后一个存储器中，
		// 可在后续块中使用。世界上的其他记忆
		// 此块之后的序列必须为死序列，因为只有
		// 一个记忆活了。
		bEnd.Values = append(bEnd.Values, last)
		last.Block = bEnd
		last.reset(OpPhi)
		last.Pos = last.Pos.WithNotStmt()
		last.Type = types.TypeMem
		last.AddArg(memThen)
		last.AddArg(memElse)
		for _, w := range stores {
			if w != last {
				w.resetArgs()
			}
		}
		for _, w := range stores {
			if w != last {
				f.freeValue(w)
			}
		}

		// 将存储序列后的值放入结束块
		bEnd.Values = append(bEnd.Values, after...)
		for _, w := range after {
			w.Block = bEnd
		}

		// 在加载写操作之间，抢占是不安全的
		// 屏障启用标志并执行写入
		// 因为这将允许GC相变，
		// 这会使国旗失效。记住
		// 条件块，以便活动性分析可以禁用
		// 安全点。这有点微妙，因为我们
		// 自下而上拆分b。
		if firstSplit {
			// 加上b本身。
			b.Func.WBLoads = append(b.Func.WBLoads, b)
			firstSplit = false
		} else {
			// 我们已经分开了b，所以我们只推了a
			// 将屏障测试写入弯管。
			b.Func.WBLoads = append(b.Func.WBLoads, bEnd)
		}

		// 如果我们在这个街区有更多的商店，再做一次这个街区
		if nWBops > 0 {
			goto again
		}
	}
}

// computeZeroMap返回从内存值的ID到的映射
// 已知在该内存值处归零的一组位置。
func (f *Func) computeZeroMap() map[ID]ZeroRegion {
	ptrSize := f.Config.PtrSize
	// 跟踪内存中已知为零的部分。
	// 这有助于消除各种初始化模式的写入障碍。
	// 这种分析是保守的。对于每个内存状态，我们只跟踪
	// 已知单个对象的前64个字中的哪一个为零。
	zeroes := map[ID]ZeroRegion{}
	// 查找新对象。
	for _, b := range f.Blocks {
		for _, v := range b.Values {
			if mem, ok := IsNewObject(v); ok {
				nptr := v.Type.Elem().Size() / ptrSize
				if nptr > 64 {
					nptr = 64
				}
				zeroes[mem.ID] = ZeroRegion{base: v, mask: 1<<uint(nptr) - 1}
			}
		}
	}
	// 查找这些新对象的存储。
	for {
		changed := false
		for _, b := range f.Blocks {
			// 注意：向前迭代有助于收敛，因为值是
			// 通常（但不总是！）按门店顺序。
			for _, v := range b.Values {
				if v.Op != OpStore {
					continue
				}
				z, ok := zeroes[v.MemoryArg().ID]
				if !ok {
					continue
				}
				ptr := v.Args[0]
				var off int64
				size := v.Aux.(*types.Type).Size()
				for ptr.Op == OpOffPtr {
					off += ptr.AuxInt
					ptr = ptr.Args[0]
				}
				if ptr != z.base {
					// 不同的基本对象-我们什么都不知道。
					// 我们甚至可以向已知的基本对象写入数据
					// 关于，但通过别名但偏移的指针。
					// 所以我们必须扔掉所有的零信息。
					continue
				}
				// 圆形以覆盖任何部分写入的指针插槽。
				// 指针写入永远不应该像这样不对齐，而应该是非指针写入
				// 此指针类型将执行包含写入的操作。
				if d := off % ptrSize; d != 0 {
					off -= d
					size += d
				}
				if d := size % ptrSize; d != 0 {
					size += ptrSize - d
				}
				// 剪辑到我们跟踪的64个单词。
				min := off
				max := off + size
				if min < 0 {
					min = 0
				}
				if max > 64*ptrSize {
					max = 64 * ptrSize
				}
				// 为我们正在编写的部分清除位（因此
				// 不再一定是零）。
				for i := min; i < max; i += ptrSize {
					bit := i / ptrSize
					z.mask &^= 1 << uint(bit)
				}
				if z.mask == 0 {
					// 没有更多已知的零-不要费心保留。
					continue
				}
				// 为新存储保存更新的已知零内容。
				if zeroes[v.ID] != z {
					zeroes[v.ID] = z
					changed = true
				}
			}
		}
		if !changed {
			break
		}
	}
	if f.pass.debug > 0 {
		fmt.Printf("func %s\n", f.Name)
		for mem, z := range zeroes {
			fmt.Printf("  memory=v%d ptr=%v zeromask=%b\n", mem, z.base, z.mask)
		}
	}
	return zeroes
}

// wbcall在b中发出写屏障运行时调用，返回内存。
func wbcall(pos src.XPos, b *Block, fn, typ *obj.LSym, ptr, val, mem, sp, sb *Value) *Value {
	config := b.Func.Config

	var wbargs []*Value
	// TODO（注册参数）这有点像黑客。
	inRegs := b.Func.ABIDefault == b.Func.ABI1 && len(config.intParamRegs) >= 3

	// 将参数放在堆栈上
	off := config.ctxt.FixedFrameSize()

	var argTypes []*types.Type
	if typ != nil { // 对于类型dmemmove
		taddr := b.NewValue1A(pos, OpAddr, b.Func.Config.Types.Uintptr, typ, sb)
		argTypes = append(argTypes, b.Func.Config.Types.Uintptr)
		off = round(off, taddr.Type.Alignment())
		if inRegs {
			wbargs = append(wbargs, taddr)
		} else {
			arg := b.NewValue1I(pos, OpOffPtr, taddr.Type.PtrTo(), off, sp)
			mem = b.NewValue3A(pos, OpStore, types.TypeMem, ptr.Type, arg, taddr, mem)
		}
		off += taddr.Type.Size()
	}

	argTypes = append(argTypes, ptr.Type)
	off = round(off, ptr.Type.Alignment())
	if inRegs {
		wbargs = append(wbargs, ptr)
	} else {
		arg := b.NewValue1I(pos, OpOffPtr, ptr.Type.PtrTo(), off, sp)
		mem = b.NewValue3A(pos, OpStore, types.TypeMem, ptr.Type, arg, ptr, mem)
	}
	off += ptr.Type.Size()

	if val != nil {
		argTypes = append(argTypes, val.Type)
		off = round(off, val.Type.Alignment())
		if inRegs {
			wbargs = append(wbargs, val)
		} else {
			arg := b.NewValue1I(pos, OpOffPtr, val.Type.PtrTo(), off, sp)
			mem = b.NewValue3A(pos, OpStore, types.TypeMem, val.Type, arg, val, mem)
		}
		off += val.Type.Size()
	}
	off = round(off, config.PtrSize)
	wbargs = append(wbargs, mem)

	// 发出通知
	call := b.NewValue0A(pos, OpStaticCall, types.TypeResultMem, StaticAuxCall(fn, b.Func.ABIDefault.ABIAnalyzeTypes(nil, argTypes, nil)))
	call.AddArgs(wbargs...)
	call.AuxInt = off - config.ctxt.FixedFrameSize()
	return b.NewValue1I(pos, OpSelectN, types.TypeMem, 0, call)
}

// 四舍五入到r的倍数，r是2的幂
func round(o int64, r int64) int64 {
	return (o + r - 1) &^ (r - 1)
}

// IsStackAddr报告是否已知v是堆栈插槽的地址。
func IsStackAddr(v *Value) bool {
	for v.Op == OpOffPtr || v.Op == OpAddPtr || v.Op == OpPtrIndex || v.Op == OpCopy {
		v = v.Args[0]
	}
	switch v.Op {
	case OpSP, OpLocalAddr, OpSelectNAddr:
		return true
	}
	return false
}

// IsGlobalAddress报告v是否已知为全局地址（或零）。
func IsGlobalAddr(v *Value) bool {
	if v.Op == OpAddr && v.Args[0].Op == OpSB {
		return true // 全球银行的地址
	}
	if v.Op == OpConstNil {
		return true
	}
	if v.Op == OpLoad && IsReadOnlyGlobalAddr(v.Args[0]) {
		return true // 从只读全局加载-生成的地址不能是堆地址。
	}
	return false
}

// IsReadOnlyGlobalAddr报告是否已知v是只读全局地址。
func IsReadOnlyGlobalAddr(v *Value) bool {
	if v.Op == OpConstNil {
		// 零指针是只读的。见第33438期。
		return true
	}
	if v.Op == OpAddr && v.Aux.(*obj.LSym).Type == objabi.SRODATA {
		return true
	}
	return false
}

// IsNewObject报告v是否是指向新分配的零对象的指针，
// 如果是，还返回v为零的内存状态mem。
func IsNewObject(v *Value) (mem *Value, ok bool) {
	f := v.Block.Func
	c := f.Config
	if f.ABIDefault == f.ABI1 && len(c.intParamRegs) >= 1 {
		if v.Op != OpSelectN || v.AuxInt != 0 {
			return nil, false
		}
		// 找到记忆
		for _, w := range v.Block.Values {
			if w.Op == OpSelectN && w.AuxInt == 1 && w.Args[0] == v.Args[0] {
				mem = w
				break
			}
		}
		if mem == nil {
			return nil, false
		}
	} else {
		if v.Op != OpLoad {
			return nil, false
		}
		mem = v.MemoryArg()
		if mem.Op != OpSelectN {
			return nil, false
		}
		if mem.Type != types.TypeMem {
			return nil, false
		} // 如果为true，则假定它是正确的选择
	}
	call := mem.Args[0]
	if call.Op != OpStaticCall {
		return nil, false
	}
	if !isSameCall(call.Aux, "runtime.newobject") {
		return nil, false
	}
	if f.ABIDefault == f.ABI1 && len(c.intParamRegs) >= 1 {
		if v.Args[0] == call {
			return mem, true
		}
		return nil, false
	}
	if v.Args[0].Op != OpOffPtr {
		return nil, false
	}
	if v.Args[0].Args[0].Op != OpSP {
		return nil, false
	}
	if v.Args[0].AuxInt != c.ctxt.FixedFrameSize()+c.RegSize { // 返回值的偏移量
		return nil, false
	}
	return mem, true
}

// IsSanitizerSafeAddr报告v是否为已知地址
// 这不需要仪器。
func IsSanitizerSafeAddr(v *Value) bool {
	for v.Op == OpOffPtr || v.Op == OpAddPtr || v.Op == OpPtrIndex || v.Op == OpCopy {
		v = v.Args[0]
	}
	switch v.Op {
	case OpSP, OpLocalAddr, OpSelectNAddr:
		// 堆栈地址总是安全的。
		return true
	case OpITab, OpStringPtr, OpGetClosurePtr:
		// ITAB、字符串数据和闭包字段是
		// 只读初始化一次。
		return true
	case OpAddr:
		return v.Aux.(*obj.LSym).Type == objabi.SRODATA
	}
	return false
}

// isVolatile报告v是否是指向堆栈上的参数区域的指针
// 将被函数调用破坏。
func isVolatile(v *Value) bool {
	for v.Op == OpOffPtr || v.Op == OpAddPtr || v.Op == OpPtrIndex || v.Op == OpCopy || v.Op == OpSelectNAddr {
		v = v.Args[0]
	}
	return v.Op == OpSP
}
